package recursion;

public class Fibonacci {
    // 前两项和相加等于这一项
    public static int fibonacciBasic(int num) {
        if (num == 1) {
            return 1;
        }
        if (num == 0) {
            return 0;
        }
        return fibonacciBasic(num - 1) + fibonacciBasic(num - 2);
    }
// 设立一个缓存机制 把得出的结果缓存到数组 memoitation 记忆法或者备忘录
    public static int fibonacci(int num) {
        if (num == 0) {
            return 0;
        }
        int[] cache = new int[num+1];
        for (int i = 0, len = cache.length; i < len; i++) {
            cache[i] = -1;
        }
        cache[0] = 0;
        cache[1] = 1;
        return f(num, cache);
    }

    public static int f(int num, int[] cache) {
        if(cache[num]!=-1){
            return  cache[num];
        }
        int x = f(num-1,cache);
        int y = f(num-2,cache);
        cache[num] = x+y;
        return  cache[num];
    }

    public static void main(String[] args) {
        fibonacciBasic(800);
    }
}
